Phân cụm phân cấp là gì? Các nghiên cứu khoa học liên quan

Khái niệm phân cụm phân cấp

Phân cụm phân cấp là một phương pháp học không giám sát xây dựng cấu trúc phân nhóm dạng cây để mô tả mối quan hệ giữa các đối tượng dựa trên mức độ tương đồng. Thay vì yêu cầu số cụm ngay từ đầu, phương pháp này tạo ra một hệ thống phân cấp theo nhiều lớp, trong đó các cụm nhỏ được hợp nhất thành cụm lớn hơn hoặc ngược lại tùy theo chiến lược thuật toán. Đặc điểm này giúp phân cụm phân cấp trở thành công cụ quan trọng trong phân tích dữ liệu mang tính phân tầng.

Phân cụm phân cấp dựa trên ma trận khoảng cách giữa các điểm dữ liệu và một tiêu chí liên kết quy định cách hai cụm được gộp lại. Sự linh hoạt này cho phép mô tả cấu trúc dữ liệu phức tạp mà các phương pháp như k-means không thể thể hiện. Một đặc điểm khác là khả năng biểu diễn toàn bộ quá trình phân nhóm thông qua sơ đồ dendrogram, giúp người dùng hiểu rõ lịch sử hình thành cụm và đưa ra quyết định cắt cụm hợp lý.

Phân cụm phân cấp có hai dạng chính: gộp (agglomerative) và tách (divisive). Phương pháp gộp bắt đầu với từng điểm riêng lẻ và hợp nhất dần, trong khi phương pháp tách đi từ một cụm lớn duy nhất và chia nhỏ dần. Bảng dưới đây mô tả sự khác biệt tổng quát:

Dạng phân cụm	Quy trình	Đặc điểm
Gộp	Hợp nhất các cụm gần nhau nhất	Phổ biến, dễ triển khai
Tách	Tách cụm lớn thành các cụm nhỏ	Độ chính xác cao nhưng tốn chi phí

Phương pháp gộp được sử dụng chủ yếu trong các thư viện học máy như Scikit-learn.

Các dạng phân cụm phân cấp

Hai dạng phân cụm phân cấp gồm phương pháp gộp và phương pháp tách, mỗi dạng có cách tiếp cận riêng đối với cấu trúc dữ liệu. Phân cụm gộp là quá trình lặp từng bước, trong đó mỗi điểm ban đầu được xem là một cụm độc lập và sau đó các cụm gần nhau nhất được hợp nhất. Quá trình tiếp tục cho đến khi tất cả điểm thuộc cùng một cụm. Đây là phương pháp phổ biến vì tính đơn giản, dễ áp dụng và khả năng xử lý dữ liệu kích thước trung bình.

Phân cụm tách hoạt động theo chiều ngược lại: bắt đầu với một cụm duy nhất chứa toàn bộ dữ liệu và phân tách dần thành các cụm nhỏ hơn theo tiêu chí sai khác tăng dần. Dù phương pháp tách mang tính mô tả tốt hơn và có thể tạo ra cấu trúc phân cấp tinh vi hơn, chi phí tính toán rất cao, thường vượt quá khả năng của hệ thống khi dữ liệu lớn. Điều này khiến nó ít được triển khai trong thư viện học máy hơn so với phương pháp gộp.

Các dạng phân cụm phân cấp còn có thể phân theo tiêu chí liên kết hoặc loại dữ liệu đầu vào. Danh sách dưới đây mô tả các phân nhóm thường gặp:

• Phân cấp đơn liên kết: tập trung vào khoảng cách ngắn nhất.
• Phân cấp hoàn liên kết: tập trung vào khoảng cách dài nhất.
• Phân cấp trung bình liên kết: sử dụng khoảng cách trung bình.
• Phân cấp dựa trên phương sai như Ward linkage.

Những biến thể này làm tăng tính linh hoạt của phương pháp phân cụm phân cấp trong nhiều lĩnh vực khoa học dữ liệu.

Khoảng cách và tiêu chí liên kết

Khoảng cách là yếu tố trung tâm trong phân cụm phân cấp vì nó xác định mức độ khác biệt giữa các điểm dữ liệu. Khoảng cách Euclid được sử dụng rộng rãi cho dữ liệu dạng số, trong khi khoảng cách Manhattan phù hợp với dữ liệu có cấu trúc lưới hoặc phân bố đều. Với dữ liệu văn bản hoặc dữ liệu đặc trưng vector hóa, khoảng cách Cosine được lựa chọn để đo mức độ tương đồng về hướng thay vì độ lớn.

Ma trận khoảng cách là đầu vào quan trọng nhất của thuật toán gộp. Giá trị trong ma trận này quyết định thứ tự cụm được hợp nhất và chiều sâu của dendrogram. Khi thay đổi thước đo khoảng cách, hình dạng phân cụm có thể thay đổi đáng kể. Vì vậy, lựa chọn thước đo phù hợp đóng vai trò quyết định trong phân tích dữ liệu.

Tiêu chí liên kết quy định cách tính khoảng cách giữa hai cụm. Một số phương pháp liên kết phổ biến:

• Single linkage: chọn khoảng cách nhỏ nhất giữa các điểm thuộc hai cụm.
• Complete linkage: chọn khoảng cách lớn nhất giữa hai cụm.
• Average linkage: sử dụng giá trị trung bình của toàn bộ khoảng cách.
• Ward linkage: tối thiểu hóa phương sai nội cụm, giúp tạo cụm đồng nhất.

Bảng sau minh họa đặc trưng của từng tiêu chí:

Tiêu chí liên kết	Ưu điểm	Nhược điểm
Single linkage	Tìm cụm dạng chuỗi hiệu quả	Dễ bị nhiễu và tạo cụm kéo dài
Complete linkage	Tạo cụm nhỏ gọn	Nhạy cảm với điểm ngoại lai
Average linkage	Cân bằng giữa single và complete;	Có thể làm mờ ranh giới cụm
Ward linkage	Tối ưu hóa đồng nhất cụm	Không phù hợp với dữ liệu không thuộc không gian Euclid

Cấu trúc dendrogram

Dendrogram là biểu đồ dạng cây mô tả quá trình gộp hoặc tách cụm, thể hiện mối quan hệ phân cấp giữa các điểm dữ liệu. Trục đứng của dendrogram biểu thị độ sai khác hoặc khoảng cách tại thời điểm cụm được hợp nhất. Khi một nhánh nằm ở độ cao lớn, điều đó cho thấy hai cụm được hợp nhất có mức độ khác biệt cao.

Dendrogram giúp phân tích cấu trúc dữ liệu theo nhiều tầng mức. Người dùng có thể chọn ngưỡng cắt để xác định số cụm phù hợp nhất mà không cần chỉ định trước. Tính trực quan của dendrogram hỗ trợ mô tả phân bố dữ liệu và phát hiện cấu trúc tiềm ẩn mà các phương pháp khác khó mô tả.

Các công cụ trực quan hóa dendrogram được tích hợp trong nhiều phần mềm phân tích dữ liệu, bao gồm môi trường MATLAB do MathWorks phát triển. Những công cụ này cho phép phóng to, thu nhỏ và đánh dấu các mức cắt, giúp cải thiện khả năng giải thích kết quả.

Thuật toán phân cụm phân cấp

Thuật toán phân cụm phân cấp gồm hai nhánh chính: gộp (agglomerative) và tách (divisive). Thuật toán gộp được sử dụng rộng rãi hơn vì tính đơn giản và khả năng hoạt động hiệu quả với quy mô dữ liệu vừa và nhỏ. Quy trình gộp bắt đầu bằng việc xem mỗi điểm dữ liệu là một cụm riêng biệt, sau đó tìm hai cụm gần nhau nhất theo ma trận khoảng cách và hợp nhất chúng lại. Sau mỗi lần hợp nhất, ma trận khoảng cách được cập nhật theo tiêu chí liên kết đã lựa chọn, tiếp tục cho đến khi toàn bộ dữ liệu thuộc một cụm duy nhất.

Thuật toán tách hoạt động ngược lại. Thay vì hợp nhất, nó bắt đầu với một cụm duy nhất chứa toàn bộ dữ liệu, sau đó tách cụm thành hai nhóm theo tiêu chí phân tách tối ưu. Quá trình lặp lại cho đến khi đạt số cụm mong muốn. Phương pháp tách mô tả cấu trúc phân cấp chi tiết hơn nhưng chi phí tính toán cao, thường tăng theo cấp số mũ khi kích thước dữ liệu tăng. Do đó, nó ít được sử dụng trong các ứng dụng yêu cầu tốc độ.

Thuật toán gộp có thể được biểu diễn bằng công thức cập nhật khoảng cách: $d(C_{new}, C_k) = f(d(C_i, C_k), d(C_j, C_k))$ Trong đó $C_{new}$ là cụm mới hình thành từ $C_i$ và $C_j$, và hàm $f$ phụ thuộc vào phương pháp liên kết. Bảng sau mô tả độ phức tạp tính toán của từng dạng:

Dạng thuật toán	Độ phức tạp trung bình	Ứng dụng
Gộp	O(n² log n)	Khoa học dữ liệu, sinh học phân tử
Tách	O(2^n)	Nghiên cứu chuyên sâu, dữ liệu nhỏ

Ưu điểm của phân cụm phân cấp

Phân cụm phân cấp mang lại khả năng mô tả sâu cấu trúc dữ liệu nhờ tạo ra hệ thống phân cấp đa tầng. Không giống như k-means, phương pháp này không yêu cầu xác định số cụm ban đầu, nhờ đó giúp việc khám phá dữ liệu trở nên linh hoạt hơn. Điều này đặc biệt hữu ích khi dữ liệu có cấu trúc phân bố phức tạp hoặc khi chưa có giả định rõ ràng về số cụm.

Dendrogram là một trong những ưu điểm nổi bật nhất của phương pháp phân cấp. Người dùng có thể trực tiếp quan sát mối quan hệ giữa các điểm dữ liệu, đánh giá độ tương đồng theo nhiều cấp độ và đưa ra quyết định cắt cụm hợp lý. Khả năng quan sát trực quan này giúp cải thiện phân tích thăm dò dữ liệu, hỗ trợ phát hiện các nhóm ẩn mà các thuật toán khác bỏ sót.

Phân cụm phân cấp cũng có độ ổn định tốt vì không phụ thuộc vào khởi tạo ngẫu nhiên. Điều này khác biệt với k-means vốn dễ bị ảnh hưởng bởi vị trí điểm khởi tạo. Ngoài ra, phân cụm phân cấp xử lý tốt dữ liệu không hình cầu, nơi các cụm có thể kéo dài hoặc phân tầng phức tạp. Một số ưu điểm có thể liệt kê:

• Không yêu cầu xác định số cụm ban đầu.
• Biểu diễn quan hệ phân cấp rõ ràng qua dendrogram.
• Hoạt động ổn định với dữ liệu phức tạp.
• Linh hoạt nhờ nhiều tiêu chí liên kết.

Nhược điểm của phân cụm phân cấp

Dù có nhiều ưu thế, phân cụm phân cấp cũng tồn tại những hạn chế đáng kể. Chi phí tính toán cao là một trong những điểm yếu lớn nhất, đặc biệt với bộ dữ liệu lớn. Việc tính toán ma trận khoảng cách kích thước n×n và cập nhật liên tục trong từng bước hợp nhất khiến thuật toán tiêu tốn nhiều tài nguyên bộ nhớ và thời gian. Điều này làm giảm hiệu quả khi triển khai trên hệ thống lớn hoặc trong xử lý dữ liệu thời gian thực.

Một nhược điểm khác là tính "không đảo ngược". Khi hai cụm đã được hợp nhất, thuật toán không thể sửa lại quyết định này ngay cả khi các bước tiếp theo cho thấy đó là lựa chọn sai. Điều này khiến kết quả dễ bị ảnh hưởng nếu có nhiễu hoặc điểm ngoại lai trong dữ liệu, đặc biệt với single linkage vốn dễ tạo ra hiệu ứng "chuỗi" kéo dài cụm không mong muốn.

Phân cụm phân cấp cũng khó xử lý dữ liệu không đồng nhất hoặc dữ liệu có kích thước rất lớn. Khi số chiều cao, thước đo khoảng cách có thể trở nên kém hiệu quả do ảnh hưởng của "lời nguyền chiều cao". Tóm lược hạn chế:

• Chi phí tính toán và bộ nhớ lớn.
• Không thể điều chỉnh sai sót trong quá trình gộp cụm.
• Nhạy cảm với nhiễu khi dùng tiêu chí single linkage.
• Hiệu suất giảm với dữ liệu nhiều chiều.

Ứng dụng của phân cụm phân cấp

Phân cụm phân cấp được ứng dụng rộng rãi trong khoa học dữ liệu, sinh học phân tử, phân tích thị trường, xử lý ngôn ngữ tự nhiên và khai phá dữ liệu. Trong sinh học phân tử, phương pháp này giúp phân tích dữ liệu gene, xây dựng cây phân loại sinh học và xác định quan hệ tiến hóa giữa các loài. Dendrogram hỗ trợ trực quan hóa mối quan hệ gene hoặc protein, cho phép phát hiện các nhóm chức năng.

Trong khoa học dữ liệu, phân cụm phân cấp là công cụ quan trọng trong phân tích khám phá (EDA). Nó giúp nhận diện cấu trúc ẩn trong dữ liệu trước khi áp dụng các thuật toán phức tạp hơn. Trong marketing, phương pháp này hỗ trợ phân nhóm khách hàng dựa trên hành vi mua sắm, giúp thiết kế chiến lược tiếp thị mục tiêu.

Phân cụm phân cấp cũng được sử dụng trong xử lý ngôn ngữ tự nhiên để phân nhóm văn bản, trích xuất chủ đề và phát hiện tài liệu tương đồng. Trong an ninh mạng, nó hỗ trợ phân tích mẫu log hệ thống để xác định các nhóm hành vi bất thường. Một số ứng dụng tiêu biểu:

• Nhóm gene và protein trong sinh học phân tử.
• Phân nhóm khách hàng trong thương mại.
• Phân tích văn bản trong NLP.
• Phân tích log và phát hiện bất thường trong an ninh mạng.

So sánh phân cụm phân cấp với các phương pháp khác

Phân cụm phân cấp thường được so sánh với k-means, DBSCAN và Gaussian Mixture Models (GMM). K-means có tốc độ nhanh hơn nhưng yêu cầu xác định số cụm trước và khó xử lý cụm không hình cầu. DBSCAN phát hiện tốt các cụm mật độ cao và điểm nhiễu nhưng hoạt động kém nếu mật độ cụm không nhất quán. GMM linh hoạt với dữ liệu phân bố phức tạp nhưng cần tối ưu nhiều tham số.

Phân cụm phân cấp không yêu cầu số cụm ban đầu, cung cấp cấu trúc phân cấp rõ ràng và hoạt động ổn định hơn. Tuy nhiên, chi phí tính toán lớn hạn chế khả năng mở rộng. Tùy vào dữ liệu và mục tiêu, phân cụm phân cấp có thể là bước khởi đầu tốt để khám phá cấu trúc trước khi áp dụng thuật toán nhanh hơn.

Bảng so sánh sau minh họa điểm khác biệt:

Thuật toán	Ưu điểm	Nhược điểm
Hierarchical Clustering	Cấu trúc phân cấp trực quan, không cần số cụm	Chi phí tính toán cao
K-means	Nhanh, dễ mở rộng	Cần số cụm trước, nhạy cảm với khởi tạo
DBSCAN	Phát hiện nhiễu tốt, không cần số cụm	Khó tối ưu tham số với dữ liệu không đồng nhất

Tài liệu tham khảo

• Scikit-learn. Clustering Algorithms Overview. Truy cập tại: https://scikit-learn.org/stable/modules/clustering.html
• MathWorks. Clustering and Dendrograms. Truy cập tại: https://www.mathworks.com/discovery/clustering.html
• IBM. Introduction to Clustering Methods. Truy cập tại: https://www.ibm.com/topics/clustering